package com.wxweven.algorithm.string;

/**
 * @author wxweven
 */
public class LC05最长回文子串 {

    /*
     * 给你一个字符串 s，找到 s 中最长的回文子串。
     *
     * 示例 1：
     * 输入：s = "babad"
     * 输出："bab"
     * 解释："aba" 同样是符合题意的答案。
     *
     * 示例 2：
     * 输入：s = "cbbd"
     * 输出："bb"
     *
     * 示例 3：
     * 输入：s = "a"
     * 输出："a"
     *
     * 示例 4：
     * 输入：s = "ac"
     * 输出："a"
     *
     * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
     *
     * 题解：https://mp.weixin.qq.com/s/ux6VSWAPwgOS32xlScr2kQ
     */

    public String longestPalindrome(String s) {
        String result = "";


        for (int i = 0; i < s.length(); i++) {

            // 找到以 s[i] 为中心的回文串
            // 找到以 s[i] 和 s[i+1] 为中心的回文串
            String s1 = helper(s, i, i);
            // 处理长度为偶数的 如abba这种情况，没有一个中心字符
            String s2 = helper(s, i, i + 1);

            String tmp = s1.length() > s2.length() ? s1 : s2;
            if (result.length() < tmp.length()) {
                result = tmp;
            }
        }

        return result;
    }

    /*
     *  核心思想是：从中间开始向两边扩散来判断回文串
     */
    public String helper(String s, int left, int right) {
        /*
         * 循环结束的条件（满足任意一个）：
         * 1: left 越界，即 left <0
         * 2: right 越界，即 right >= s.length()
         * 3: left 和 right 指向的字符不相等
         */
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }

        // 循环退出时，left 已经做了--，所以这里的left 需要加1
        // 而substring方法中，right 本来就是exclusive的，所以不需要加1
        return s.substring(left + 1, right);
    }
}